package main

import (
	"fmt"
)

func main() {
	insertSortSelf()
}

func insertSortSelf() {
	//获得一个数组
	numbers := []int{5, 7, 1, 3, 0, 2, 6, 9, 4, 8} //utils.GetRandSlices(10, 5)
	length := len(numbers)
	fmt.Printf("获取到 %d 一个元素数组：\n%v\n", length, numbers)
	//开始排序
	//将数据插入一个已经`排好序的序列`里边，并更具其大小插入到合适的位置，直到所有数列插入完成。插入时一排好序数据需要按照条件向后移动，为插入数据保留空间。
	for i := 1; i < length; i++ {
		//当前位置
		//依次插入。
		insertIndex := i
		tmp := numbers[i]
		for j := i; j > 0; j-- {
			//如果满足条件，设置插入位置。
			if tmp < numbers[j-1] {
				insertIndex = j - 1
				numbers[j] = numbers[j-1] //将数据向后移动一位，为插入数据获得空间。
			} else {
				break //没有合适的位置，退出本次插入
			}
		}
		numbers[insertIndex] = tmp
		fmt.Printf("第 %d 次，获取到插入位置：%d ，插入数据：%d\n\n%v\n\n", i, insertIndex, numbers[insertIndex], numbers)
	}
	fmt.Printf("\n%v ", numbers)
}
func insertSort() {
	//获得一个数组
	numbers := []int{5, 7, 1, 3, 0, 2, 6, 9, 4, 8} //utils.GetRandSlices(10, 5)
	length := len(numbers)
	fmt.Printf("获取到 %d 一个元素数组：\n%v\n", length, numbers)
	//开始排序
	//将数据插入一个已经`排好序的序列`里边，并更具其大小插入到合适的位置，直到所有数列插入完成。插入时一排好序数据需要按照条件向后移动，为插入数据保留空间。

	//准备一个已经排好序的序列
	sorted := make([]int, length)
	sorted[0] = numbers[0] //第一位插入数据无需排序
	//fmt.Printf("%v",sorted)
	for i := 1; i < length; i++ {
		//当前位置
		//依次插入。
		insertIndex := i
		for j := i; j > 0; j-- {
			//如果满足条件，设置插入位置。
			if numbers[i] < sorted[j-1] {
				insertIndex = j - 1
				sorted[j] = sorted[j-1] //将数据向后移动一位，为插入数据获得空间。
			} else {
				break //没有合适的位置，退出本次插入
			}
		}
		sorted[insertIndex] = numbers[i]
		fmt.Printf("第 %d 次，获取到插入位置：%d ，插入数据：%d\n\n%v\n\n", i, insertIndex, sorted[insertIndex], sorted)
	}
	numbers = sorted
	fmt.Printf("\n%v ", numbers)
}
